﻿using System;
using System.Collections.Generic;

namespace SortOf
{
    public static class BinarySearch
    {
        public static int BinSearch<T>(T[] array, T value) where T : IComparable
        {
            int upperBound, lowerBound, middle;
            upperBound = (array.Length - 1);
            lowerBound = 0;

            // Continue as long as the lowerBound is lower or equal to upperBound.
            while (lowerBound <= upperBound)
            {
                // This is the middle of the array!
                middle = ((upperBound + lowerBound) / 2);

                // The result
                int compare = value.CompareTo(array[middle]);

                // We managed to find a matching number.
                if (compare == 0)
                {
                    return middle;
                }
                else
                {
                    // When the value is lower then the value that is in the middle (index).
                    if (compare < 0)
                    {
                        // Divide our current range by lowering the upperBound to the middle.
                        upperBound = (middle - 1);
                    }
                    else
                    {
                        // Divide our current range by uppering the lowerBound to the middle.
                        lowerBound = (middle + 1);
                    }
                }
            }

            return -1;
        }

        public static int RbinSearch(IComparable[] mynums, IComparable value, int lower, int upper)
        {
            if (lower > upper)
            {
                return -1;
            }
            else
            {
                int mid;
                mid = (int)(upper + lower) / 2;
                int compare = value.CompareTo(mynums[mid]);
                if (compare < 0)
                {
                    return RbinSearch(mynums, value, lower, mid - 1);
                }
                else if (value == mynums[mid])
                {
                    return mid;
                }
                else
                {
                    return RbinSearch(mynums, value, mid + 1, upper);
                }
            }
        }
    }
}
